package linkedin;

import java.util.*;

/**
 * Created by Tzachi on 27/10/2014.
 * <p>
 * Given a list of tuples representing intervals, return the range these intervals
 * covered.
 * e.g:
 * [(1,3), (2,5),(8,9)] should return 5
 */
public class IntervalsRange {
    static class Interval {
        int start;
        int end;

        Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static int findRange(List<Interval> intervals) {
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start > o2.start) {
                    return 1;
                } else if (o2.start > o1.start) {
                    return -1;
                } else if (o1.end > o2.end) {
                    return 1;
                } else if (o2.end > o1.end) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        int range = 0;
        int s = 0;
        int i = 0;
        while (i < intervals.size()) {
            int j = i + 1;
            int currentEnd = intervals.get(i).end;
            while (j < intervals.size() && currentEnd >= intervals.get(j).start) {
                currentEnd = Math.max(currentEnd, intervals.get(j).end);
                j++;

            }
            range += currentEnd - intervals.get(s).start;
            i = j;
            s = j;
        }
        return range;
    }


    public static void main(String[] args) {
        List<Interval> intervalList = Arrays.asList(new Interval(1, 3), new Interval(2, 5), new Interval(8, 9));
        findRange(intervalList);
    }
}
